package digui;

public class Fibo2 {
    static int fibo2(int n){
        if (n <= 2) return 1;
        int[] arr = new int[n + 1];
        arr[1]=arr[2]=1;
        return opt_arr(n, arr);
    }

    static int opt_arr(int n, int[] arr){
        if (arr[n] == 0) {
            arr[n] = opt_arr(n-1, arr) + opt_arr(n-2, arr);
        }
        return arr[n];
    }



    public static void main(String[] args) {
        System.out.println(fibo2(3));
        System.out.println(fibo2(4));
        System.out.println(fibo2(5));
        System.out.println(fibo2(6));
        System.out.println(fibo2(7));
        System.out.println(fibo2(8));
    }
}
